package com.cat.dataStructure02;

import java.util.*;

/**
*   @description https://leetcode.cn/problems/distribute-elements-into-two-arrays-ii/
*   @author 曲大人的喵
*   @create 2025/10/31 20:51
*   @since JDK17
*/

class Fenwick {
    private final int[] tree;
    public Fenwick(int n) {
        tree = new int[n];
    }

    void add(int i) {
        while (i < tree.length) {
            tree[i]++;
            i += i & -i;
        }
    }
    int pre(int i) {
        int ans = 0;
        while (i > 0) {
            ans += tree[i];
            i -= i & -i;
        }
        return ans;
    }
}

class Solution89 {
    public int[] resultArray(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        l1.add(nums[0]);
        l2.add(nums[1]);
        int n = nums.length;
        Fenwick t1 = new Fenwick(n + 1), t2 = new Fenwick(n + 1);
        t1.add(Arrays.binarySearch(sorted, nums[0]) + 1);
        t2.add(Arrays.binarySearch(sorted, nums[1]) + 1);
        for (int i = 2; i < n; i++) {
            int x = nums[i];
            int y = Arrays.binarySearch(sorted, x) + 1;
            int g1 = l1.size() - t1.pre(y);
            int g2 = l2.size() - t2.pre(y);
            if (g2 > g1 || (g1 == g2 && l1.size() > l2.size())) {
                l2.add(x);
                t2.add(y);
            } else {
                l1.add(x);
                t1.add(y);
            }
        }
        l1.addAll(l2);
        for (int i = 0; i < n; i++) {
            nums[i] = l1.get(i);
        }

        return nums;
    }
}